#include <movegen.h>

#if HAVE_CONFIG_H
# include <config.h>
#endif

#include <position.h>
#include <eval.h>

#include <assert.h>
#include <string.h>
#include <stdlib.h>


#ifndef NDEBUG
// To check that data is initialized before use.
static int init = 0;
#endif


// Pawn movements by stm (WHITE == 0, BLACK == 1)
#define PAWNS_SINGLE_PUSH_SHIFT(stm) (8 - (stm) * 16)  // 8/-8
#define PAWNS_DOUBLE_PUSH_SHIFT(stm) (16 - (stm) * 32)  // 16/-16
#define PAWNS_LEFT_CAPTURE_SHIFT(stm) (7 - (stm) * 16)  // 7/-9
#define PAWNS_RIGHT_CAPTURE_SHIFT(stm) (9 - (stm) * 16)  // 9/-16


bitboard_t bb_n_attacks[64];
bitboard_t bb_k_attacks[64];
bitboard_t bb_directions[64][8];
int rays[64][64];
int up_direction[8];
int low_direction[8];


// Structure used to pass common information to the routines.
typedef struct movegen_state_t
{
  const position_t* pos;
  int stm;
  bitboard_t own;   // own pieces
  bitboard_t all;   // blockers
  bitboard_t mask;  // select possible targets

  move_t* movebuf;
  int nmoves;
} movegen_state_t;


static void init_directions()
{
  // Just to avoid relying on a particular order for the directions.
  int dir[8] = {
    EAST, NORTH_EAST, NORTH, NORTH_WEST,
    WEST, SOUTH_WEST, SOUTH, SOUTH_EAST
  };
  int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  int df[8] = {1, 1, 0, -1, -1, -1, 0, 1};


  for (int d = 0; d <8; d++) {
    for (int from = 0; from < 64; from++) {
      bitboard_t bb = 0;

      int rank = RANK(from) + dr[d];
      int file = FILE(from) + df[d];

      while (rank >= 0 && file >= 0 && rank < 8 && file < 8) {
	BB_SET(bb, SQUARE(file, rank));
	rank += dr[d];
	file += df[d];
      }

      bb_directions[from][dir[d]] = bb;
    }

    int up[4] = {NORTH, NORTH_EAST, NORTH_WEST, EAST};
    int low[4] = {SOUTH, SOUTH_WEST, SOUTH_EAST, WEST};

    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 4; j++) {
	if (up[j] == i) {
	  up_direction[i] = i;
	  low_direction[i] = low[j];
	  break;
	}
	if (low[j] == i) {
	  up_direction[i] = up[j];
	  low_direction[i] = i;
	}
      }
    }
  }

  // init rays
  for (int from = 0; from < 64; from++) {
    for (int to = 0; to < 64; to++) {
      rays[from][to] = NULL_DIRECTION;
      if (from == to)
	continue;
      else if (RANK(from) == RANK(to))
	rays[from][to] = (FILE(from) > FILE(to)
			  ? WEST
			  : EAST);
      else if (FILE(from) == FILE(to))
	rays[from][to] = (RANK(from) > RANK(to)
			  ? SOUTH
			  : NORTH);
      else if (FILE(from) - RANK(from) == FILE(to) - RANK(to))
	rays[from][to] = (RANK(from) > RANK(to)
			  ? SOUTH_WEST
			  : NORTH_EAST);
      else if (FILE(from) + RANK(from) == FILE(to) + RANK(to))
	rays[from][to] = (RANK(from) > RANK(to)
			  ? SOUTH_EAST
			  : NORTH_WEST);
    }
  }
}


static void init_knight_moves()
{
  int rankdirs[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
  int filedirs[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

  for (int rank = 0; rank < 8; rank++) {
    for (int file = 0; file < 8; file++) {
      bitboard_t bb = 0;
      for (int d = 0; d < 8; d++) {
	int r = rank + rankdirs[d];
	int f = file + filedirs[d];

	if (r >= 0 && r < 8 && f >= 0 && f < 8)
	  BB_SET(bb, SQUARE(f, r));
      }
      bb_n_attacks[SQUARE(file, rank)] = bb;
    }
  }
}


static void init_king_moves()
{
  int rankdirs[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
  int filedirs[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

  for (int rank = 0; rank < 8; rank++) {
    for (int file = 0; file < 8; file++) {
      bitboard_t bb = 0;
      for (int d = 0; d < 8; d++) {
	int r = rank + rankdirs[d];
	int f = file + filedirs[d];

	if (r >= 0 && r < 8 && f >= 0 && f < 8)
	  BB_SET(bb, SQUARE(f, r));
      }
      bb_k_attacks[SQUARE(file, rank)] = bb;
    }
  }
}


static bitboard_t slide_attacks(int from,
				bitboard_t stoppers,
				int updir,
				int lowdir)
{
  assert(init);
  assert((updir == NORTH && lowdir == SOUTH) ||
	 (updir == NORTH_EAST && lowdir == SOUTH_WEST) ||
	 (updir == NORTH_WEST && lowdir == SOUTH_EAST) ||
	 (updir == EAST && lowdir == WEST));

  bitboard_t att = bb_directions[from][updir] | bb_directions[from][lowdir];
  bitboard_t up = bb_directions[from][updir] & stoppers;
  bitboard_t low = bb_directions[from][lowdir] & stoppers;
  up = BB_SELECT_LSB(up);
  low = BB_SELECT_MSB(low | 1);
  return ((up << 1) - low) & att;
}


static void load_moves_from(int from, bitboard_t bbto, movegen_state_t* state)
{
  bbto &= state->mask;
  int n = state->nmoves;
  move_t* buf = state->movebuf;

  while (bbto) {
    buf[n++] = MAKE_MOVE(from, BB_LSB(bbto));
    BB_CLEAR_LSB(bbto);
    assert(n < MAX_N_MOVES);
  }
  state->nmoves = n;
}


static void load_moves_to(bitboard_t bbfrom, int to, movegen_state_t* state)
{
  if (!BB_TEST(state->mask, to))
    return;
  int n = state->nmoves;
  move_t* buf = state->movebuf;
  while (bbfrom) {
    int from = BB_LSB(bbfrom);
    BB_CLEAR_LSB(bbfrom);
    buf[n++] = MAKE_MOVE(from, to);
    assert(n < MAX_N_MOVES);
  }
  state->nmoves = n;
}


static void load_pawn_moves(int delta,
			    bitboard_t bbto,
			    movegen_state_t* state)
{
  bbto &= state->mask;
  int n = state->nmoves;
  move_t* buf = state->movebuf;
  bitboard_t promotions = bbto & (BB_RANK_1 | BB_RANK_8);
  int ep = position_get_ep_square(state->pos);
  while (bbto) {
    int to = BB_LSB(bbto);
    int from = to + delta;
    BB_CLEAR_LSB(bbto);
    buf[n++] = MAKE_MOVE(from, to);
    if (BB_TEST(promotions, to)) {
      SET_MOVE_PROMOTION(buf[n - 1], QUEEN);
      buf[n] = MAKE_MOVE(from, to);
      SET_MOVE_PROMOTION(buf[n], ROOK);
      ++n;
      buf[n] = MAKE_MOVE(from, to);
      SET_MOVE_PROMOTION(buf[n], BISHOP);
      ++n;
      buf[n] = MAKE_MOVE(from, to);
      SET_MOVE_PROMOTION(buf[n], KNIGHT);
      ++n;
    } else if (to == ep) {
      SET_MOVE_ENPASSANT(buf[n - 1]);
    }
    assert(n < MAX_N_MOVES);
  }
  state->nmoves = n;
}


static bitboard_t pawns_single_push(bitboard_t bb, int stm, bitboard_t all)
{
  assert(!(bb & (BB_RANK_1 | BB_RANK_8)));
  // Shift to the left or to the right according to the stm.
  bb = (bb >> 8) << (8 + PAWNS_SINGLE_PUSH_SHIFT(stm));
  return bb & ~all;
}


static bitboard_t pawns_double_push(bitboard_t bb, int stm, bitboard_t all)
{
  static const bitboard_t start[2] = {BB_RANK_2, BB_RANK_7};
  assert(!(bb & (BB_RANK_1 | BB_RANK_8)));
  bb = pawns_single_push(bb & start[stm], stm, all);
  return pawns_single_push(bb, stm, all);
}


bitboard_t movegen_pawns_left_captures(bitboard_t bb,
				       int stm,
				       bitboard_t opp)
{
  assert(!(bb & (BB_RANK_1 | BB_RANK_8)));
  // Shift to the left or to the right according to the stm.
  bb &= ~BB_FILE_A;
  bb = (bb >> 9) << (9 + PAWNS_LEFT_CAPTURE_SHIFT(stm));
  return bb & opp;
}


bitboard_t movegen_pawns_right_captures(bitboard_t bb,
					int stm,
					bitboard_t opp)
{
  assert(!(bb & (BB_RANK_1 | BB_RANK_8)));
  // Shift to the left or to the right according to the stm.
  bb &= ~BB_FILE_H;
  bb = (bb >> 7) << (7 + PAWNS_RIGHT_CAPTURE_SHIFT(stm));
  return bb & opp;
}


bitboard_t movegen_knight_attacks(int from)
{
  return bb_n_attacks[from];
}


bitboard_t movegen_bishop_attacks(int from, bitboard_t occ)
{
  bitboard_t ret;
  occ |= (BB_RANK_1 | BB_RANK_8 | BB_FILE_A | BB_FILE_H);
  ret = slide_attacks(from, occ, NORTH_WEST, SOUTH_EAST);
  ret |= slide_attacks(from, occ, NORTH_EAST, SOUTH_WEST);
  return ret;
}


bitboard_t movegen_rook_attacks(int from, bitboard_t occ)
{
  bitboard_t ret;
  ret = slide_attacks(from, occ | BB_RANK_1 | BB_RANK_8, NORTH, SOUTH);
  ret |= slide_attacks(from, occ | BB_FILE_A | BB_FILE_H, EAST, WEST);

  return ret;
}


bitboard_t movegen_king_attacks(int from)
{
  return bb_k_attacks[from];
}



static bitboard_t pawn_attackers(int stm,
				 int square,
				 const position_t* pos)
{
  bitboard_t ret = 0;
  bitboard_t bbto = BB_SINGLE(square);

  bitboard_t pawns = BB_POS_PIECES(pos, stm, PAWN);

  // pawn captures
  bitboard_t tmp;
  tmp = movegen_pawns_left_captures(pawns, stm, bbto);
  if (tmp)
    BB_SET(ret, square - PAWNS_LEFT_CAPTURE_SHIFT(stm));
  tmp = movegen_pawns_right_captures(pawns, stm, bbto);
  if (tmp)
    BB_SET(ret, square - PAWNS_RIGHT_CAPTURE_SHIFT(stm));

  return ret;
}


static bitboard_t slider_attackers(int stm,
				   int square,
				   bitboard_t all,
				   const position_t* pos)
{
  bitboard_t ret = 0;

  // rooks
  bitboard_t att;
  att = (BB_POS_PIECES(pos, stm, ROOK) |
	 BB_POS_PIECES(pos, stm, QUEEN));
  ret = att & movegen_rook_attacks(square, all);

  // bishops
  att = (BB_POS_PIECES(pos, stm, BISHOP) |
	 BB_POS_PIECES(pos, stm, QUEEN));
  ret |= att & movegen_bishop_attacks(square, all);
  return ret;
}


static bitboard_t non_slider_attackers(int stm,
				       int square,
				       bitboard_t all,
				       const position_t* pos)
{
  bitboard_t ret;

  // knights
  ret = bb_n_attacks[square] & BB_POS_PIECES(pos, stm, KNIGHT);

  // king
  ret |= bb_k_attacks[square] & BB_POS_PIECES(pos, stm, KING);

  return ret;
}


/*
 * Tell if square is attacked by some piece of stm.
 *
 * pos is only used to locate the attackers. The blockers are defined
 * by the all mask.
 */
static bitboard_t attackers(int stm,
			    int square,
			    bitboard_t all,
			    const position_t* pos)
{
  assert(init);

  bitboard_t ret;

  ret = pawn_attackers(stm, square, pos);
  ret |= slider_attackers(stm, square, all, pos);
  ret |= non_slider_attackers(stm, square, all, pos);

  return ret;
}


static void knight_moves(int from, movegen_state_t* state)
{
  assert(init);
  bitboard_t bbto = bb_n_attacks[from] & ~state->own;
  load_moves_from(from, bbto, state);
}


static void king_moves(int from, movegen_state_t* state)
{
  assert(init);
  bitboard_t bbto = state->mask & bb_k_attacks[from] & ~state->own;
  // Check each destination square for possible attacks.
  load_moves_from(from, bbto, state);
}

static void bishop_moves(int from, movegen_state_t* state)
{
  bitboard_t bbto = movegen_bishop_attacks(from, state->all) & ~state->own;
  load_moves_from(from, bbto, state);
}


static void rook_moves(int from, movegen_state_t* state)
{
  bitboard_t bbto = movegen_rook_attacks(from, state->all) & ~state->own;
  load_moves_from(from, bbto, state);
}


static void all_pawn_moves(bitboard_t bb, movegen_state_t* state)
{
  bitboard_t all = state->all;
  bitboard_t own = state->own;
  bitboard_t opp = (all ^ own);
  int ep = position_get_ep_square(state->pos);
  if (ep != NO_ENPASSANT)
    BB_SET(opp, ep);
  int stm = state->stm;
  bitboard_t bbto;

  bbto = pawns_single_push(bb, stm, all);
  load_pawn_moves(-PAWNS_SINGLE_PUSH_SHIFT(stm), bbto, state);

  bbto = pawns_double_push(bb, stm, all);
  load_pawn_moves(-PAWNS_DOUBLE_PUSH_SHIFT(stm), bbto, state);

  bbto = movegen_pawns_left_captures(bb, stm, opp);
  load_pawn_moves(-PAWNS_LEFT_CAPTURE_SHIFT(stm), bbto, state);

  bbto = movegen_pawns_right_captures(bb, stm, opp);
  load_pawn_moves(-PAWNS_RIGHT_CAPTURE_SHIFT(stm), bbto, state);
}


static void all_knight_moves(bitboard_t bb, movegen_state_t* state)
{
  while (bb) {
    int from = BB_LSB(bb);
    BB_CLEAR_LSB(bb);
    knight_moves(from, state);
  }
}


static void all_bishop_moves(bitboard_t bb, movegen_state_t* state)
{
  while (bb) {
    int from = BB_LSB(bb);
    BB_CLEAR_LSB(bb);
    bishop_moves(from, state);
  }
}


static void all_rook_moves(bitboard_t bb, movegen_state_t* state)
{
  while (bb) {
    int from = BB_LSB(bb);
    BB_CLEAR_LSB(bb);
    rook_moves(from, state);
  }
}


static void all_king_moves(bitboard_t bb, movegen_state_t* state)
{
  // Only up to a king is considered.
  bitboard_t k = BB_POS_PIECES(state->pos, state->stm, KING);
  king_moves(BB_LSB(k), state);
}


static void castling_moves(movegen_state_t* state)
{
  const int caps_masks[2] = {
    WCASTLE_SHORT | WCASTLE_LONG,
    BCASTLE_SHORT | BCASTLE_LONG
  };

  const position_t* pos = state->pos;
  int stm = position_get_stm(pos);
  int caps = position_get_castling_caps(pos) & caps_masks[stm];

  if (!caps)
    return;

  bitboard_t all = state->all;

  if ((caps & WCASTLE_SHORT) &&
      (!(all & (BB_SINGLE(F1) | BB_SINGLE(G1)))) &&
      BB_TEST(state->mask, F1)) {
    assert(BB_TEST(BB_POS_PIECES(pos, WHITE, KING), E1));
    assert(BB_TEST(BB_POS_PIECES(pos, WHITE, ROOK), H1));
    state->movebuf[state->nmoves++] = MOVE_WCASTLE_SHORT;
  }

  if ((caps & WCASTLE_LONG) &&
      (!(all & (BB_SINGLE(D1) | BB_SINGLE(C1) | BB_SINGLE(B1)))) &&
      BB_TEST(state->mask, C1)) {
    assert(BB_TEST(BB_POS_PIECES(pos, WHITE, KING), E1));
    assert(BB_TEST(BB_POS_PIECES(pos, WHITE, ROOK), A1));
    state->movebuf[state->nmoves++] = MOVE_WCASTLE_LONG;
  }

  if ((caps & BCASTLE_SHORT) &&
      (!(all & (BB_SINGLE(F8) | BB_SINGLE(G8)))) &&
      BB_TEST(state->mask, F8)) {
    assert(BB_TEST(BB_POS_PIECES(pos, BLACK, KING), E8));
    assert(BB_TEST(BB_POS_PIECES(pos, BLACK, ROOK), H8));
    state->movebuf[state->nmoves++] = MOVE_BCASTLE_SHORT;
  }

  if ((caps & BCASTLE_LONG) &&
      (!(all & (BB_SINGLE(D8) | BB_SINGLE(C8) | BB_SINGLE(B8)))) &&
      BB_TEST(state->mask, C8)) {
    assert(BB_TEST(BB_POS_PIECES(pos, BLACK, KING), E8));
    assert(BB_TEST(BB_POS_PIECES(pos, BLACK, ROOK), A8));
    state->movebuf[state->nmoves++] = MOVE_BCASTLE_LONG;
  }
}


static int movegen_is_pseudo_legal_nocheck(const struct position_t* pos,
					   move_t m)
{
  int stm = position_get_stm(pos);
  int from = MOVE_FROM(m);
  int to = MOVE_TO(m);
  
  if (!BB_TEST(BB_POS_COLOR(pos, stm), from))
    return 0;
  if (BB_TEST(BB_POS_COLOR(pos, stm), to))
    return 0;

  bitboard_t all = BB_POS_ALL(pos);
  bitboard_t bb;

  // Castlings.
  if (m == MOVE_WCASTLE_SHORT) {
    return ((position_get_castling_caps(pos) & WCASTLE_SHORT) &&
	    ((all & (BB_SINGLE(F1) | BB_SINGLE(G1))) == 0));
  }
  if (m == MOVE_WCASTLE_LONG) {
    return ((position_get_castling_caps(pos) & WCASTLE_LONG) &&
	    ((all & (BB_SINGLE(C1) | BB_SINGLE(D1))) == 0));
  }
  if (m == MOVE_BCASTLE_SHORT) {
    return ((position_get_castling_caps(pos) & BCASTLE_SHORT) &&
	    ((all & (BB_SINGLE(F8) | BB_SINGLE(G8))) == 0));
  }
  if (m == MOVE_BCASTLE_LONG) {
    return ((position_get_castling_caps(pos) & BCASTLE_LONG) &&
	    ((all & (BB_SINGLE(C8) | BB_SINGLE(D8))) == 0));
  }

  // Pawns.
  if (MOVE_ENPASSANT(m)) {
    return ((to == position_get_ep_square(pos)) &&
	    BB_TEST(pawn_attackers(stm, to, pos), from));
  }
  
  if (BB_TEST(BB_POS_PIECES(pos, stm, PAWN), from)) {
    if (BB_TEST(all, to)) {
      // capture
      bb = pawn_attackers(stm, to, pos);
      return BB_TEST(bb ,from);
    } else {
      // push
      bb = pawns_single_push(BB_SINGLE(from), stm, all);
      bb |= pawns_double_push(BB_SINGLE(from), stm, all);
      return BB_TEST(bb, to);
    }
  }
  
  // King or knight.
  if (BB_TEST(BB_POS_PIECES(pos, stm, KING) | 
	      BB_POS_PIECES(pos, stm, KNIGHT), from)) {
    bb = non_slider_attackers(stm, to, all, pos);
    return BB_TEST(bb, from);
  }
  
  // Queen, rook, or bishop.
  bb = slider_attackers(stm, to, all, pos);
  return BB_TEST(bb, from);
}


static int movegen_is_pseudo_legal_check(const struct position_t* pos,
					   move_t m,
					   bitboard_t king_attackers)
{
  assert(king_attackers != 0);

  // Castlings.
  if (MOVE_IS_CASTLING(m))
    return 0;

  int stm = position_get_stm(pos);
  int from = MOVE_FROM(m);
  int to = MOVE_TO(m);
  bitboard_t bb_king = BB_POS_PIECES(pos, stm, KING);

  // King.
  if (BB_TEST(bb_king, from))
    return BB_TEST(bb_k_attacks[from], to);  
  
  // If there are multiple attackers only king movements are possible.
  if (BB_IS_NOT_SINGLE(king_attackers))
    return 0;
  
  // See if the move blocks the attacker.
  int king_square = BB_LSB(bb_king);
  int attacker = BB_LSB(king_attackers);
  int direction = rays[king_square][attacker];
  if (direction == NULL_DIRECTION) {
    // The attacker is a knight: it must be captured.
    if (to != attacker)
      return 0;
  } else {
    // Capture the attacker or move between it and the king.
    if (MOVE_ENPASSANT(m)) {
      // Ok only if the attacker is the pawn that double pushed.
      int sq = position_get_ep_square(pos) - 8 + 16 * stm;
      if (sq != attacker)
	return 0;
    } else {
      bitboard_t between = (bb_directions[king_square][direction] &
			    ~bb_directions[attacker][direction]);
      assert(BB_TEST(between, attacker));
      assert(!BB_TEST(between, king_square));

      if (!BB_TEST(between, to))
	return 0;
    }
  }

  /* At this point standard verification can be used (with some
     redundancy). */
  return movegen_is_pseudo_legal_nocheck(pos, m);
}


void movegen_init()
{
  init_directions();
  init_knight_moves();
  init_king_moves();

  assert((init = 1));
}


static void movegen_moves_nocheck_impl(movegen_state_t* state)
{
  int stm = state->stm;
  const position_t* pos = state->pos;

  bitboard_t bb;

  // pawn moves
  bb = BB_POS_PIECES(pos, stm, PAWN);
  all_pawn_moves(bb, state);

  // knight moves
  bb = BB_POS_PIECES(pos, stm, KNIGHT);
  all_knight_moves(bb, state);

  // bishop moves
  bb = BB_POS_PIECES(pos, stm, BISHOP);
  bb |= BB_POS_PIECES(pos, stm, QUEEN);
  all_bishop_moves(bb, state);

  // rook moves
  bb = BB_POS_PIECES(pos, stm, ROOK);
  bb |= BB_POS_PIECES(pos, stm, QUEEN);
  all_rook_moves(bb, state);

  // king moves
  all_king_moves(BB_POS_PIECES(pos, stm, KING), state);

  // castlings
  castling_moves(state);
}


static void movegen_check_evasion_impl(movegen_state_t* state,
				       bitboard_t king_attackers)
{
  /*
   * Options:
   * - Move the king in a safe position.
   * - Capture the attacker (if lone).
   * - Move a piece between the king and the attacker (if lone).
   */

  int stm = state->stm;
  bitboard_t bb_king = BB_POS_PIECES(state->pos, stm, KING);

  // 1) Move the king.
  all_king_moves(bb_king, state);

  // In case of multiple attackers we can only move the king.
  if (BB_IS_NOT_SINGLE(king_attackers))
    return;

  /* 2) Uses the other pieces to capture the attacker.
   *
   * Pawns must be considered separately, since the other 'load_moves'
   * routines do not manage promotions and ep captures.
   */
  int attacker = BB_LSB(king_attackers);
  bitboard_t bbfrom;
  bbfrom = slider_attackers(stm, attacker, state->all, state->pos);
  bbfrom |= non_slider_attackers(stm, attacker, state->all, state->pos);
  bbfrom &= ~bb_king;
  load_moves_to(bbfrom, attacker, state);

  bitboard_t pawns = BB_POS_PIECES(state->pos, stm, PAWN);
  bitboard_t bbto;
  bbto = movegen_pawns_left_captures(pawns, stm, king_attackers);
  load_pawn_moves(-PAWNS_LEFT_CAPTURE_SHIFT(stm), bbto, state);
  bbto = movegen_pawns_right_captures(pawns, stm, king_attackers);
  load_pawn_moves(-PAWNS_RIGHT_CAPTURE_SHIFT(stm), bbto, state);
  /* If the attacker is a doubly pushed pawn we can capture the
     attacker en passant. */
  int ep = position_get_ep_square(state->pos);
  if (ep != NO_ENPASSANT &&
      BB_TEST(king_attackers, ep - 8 + stm * 16)) {
    bbto = movegen_pawns_left_captures(pawns, stm, BB_SINGLE(ep));
    load_pawn_moves(-PAWNS_LEFT_CAPTURE_SHIFT(stm), bbto, state);
    bbto = movegen_pawns_right_captures(pawns, stm, BB_SINGLE(ep));
    load_pawn_moves(-PAWNS_RIGHT_CAPTURE_SHIFT(stm), bbto, state);
  }

  /*
   * 3) Try to cover the king.
   *
   * Pawns are still treated separately.
   */
  int king_square = BB_LSB(bb_king);
  int attack_direction = rays[attacker][king_square];
  if (attack_direction == NULL_DIRECTION)
    return;

  bitboard_t between = (bb_directions[attacker][attack_direction] &
			~bb_directions[king_square][attack_direction] &
			~bb_king);

  /* Between squares are empty and can be occupied by pawn pushes or
     by an ep capture. */
  bbto = pawns_single_push(pawns, stm, state->all) & between;
  load_pawn_moves(-PAWNS_SINGLE_PUSH_SHIFT(stm), bbto, state);
  bbto = pawns_double_push(pawns, stm, state->all) & between;
  load_pawn_moves(-PAWNS_DOUBLE_PUSH_SHIFT(stm), bbto, state);

  if (ep != NO_ENPASSANT && BB_TEST(between, ep)) {
    bbto =movegen_pawns_left_captures(pawns, stm, BB_SINGLE(ep));
    load_pawn_moves(-PAWNS_LEFT_CAPTURE_SHIFT(stm), bbto, state);
    bbto = movegen_pawns_right_captures(pawns, stm, BB_SINGLE(ep));
    load_pawn_moves(-PAWNS_RIGHT_CAPTURE_SHIFT(stm), bbto, state);
  }

  // Non pawns.
  while (between) {
    int to = BB_LSB(between);
    BB_CLEAR_LSB(between);
    bbfrom = slider_attackers(stm, to, state->all, state->pos);
    bbfrom |= non_slider_attackers(stm, to, state->all, state->pos);
    bbfrom &= ~bb_king;
    load_moves_to(bbfrom, to, state);
  }
}


int movegen_legal_moves(const struct position_t* pos, move_t* buf)
{
  assert(pos != 0);
  assert(buf != 0);
  
  bitboard_t check = movegen_detect_check(pos);

  int n = 0;
  if (check)
    n = movegen_check_evasion(pos, buf);
  else
    n = movegen_moves_nocheck(pos, buf);
  
  int i = 0;
  while (i < n) {
    assert(check ? movegen_is_pseudo_legal_check(pos, buf[i], check)
	   : movegen_is_pseudo_legal_nocheck(pos, buf[i]));
    if (movegen_verify_move(pos, buf[i])) {
      ++i;
    } else {
      --n;
      buf[i] = buf[n];
    }
  }

  return n;
}


static void fill_movegen_state(const struct position_t* pos,
			       move_t* buf,
			       movegen_state_t* state)
{
  assert(pos != 0);
  assert(buf != 0);
  assert(state != 0);

  int stm = position_get_stm(pos);
  state->pos = pos;
  state->nmoves = 0;
  state->movebuf = buf;

  state->stm = stm;
  state->all = BB_POS_ALL(pos);
  state->own = BB_POS_COLOR(pos, stm);
  state->mask = ~UINT64_C(0);
}


int movegen_moves_nocheck(const struct position_t* pos, move_t* buf)
{
  assert(movegen_detect_check(pos) == 0);
  movegen_state_t state;
  fill_movegen_state(pos, buf, &state);
  movegen_moves_nocheck_impl(&state);
  return state.nmoves;
}


int movegen_captures(const struct position_t* pos, move_t* buf)
{
  assert(movegen_detect_check(pos) == 0);
  movegen_state_t state;
  fill_movegen_state(pos, buf, &state);
  state.mask = BB_POS_COLOR(pos, 1 - state.stm);
  movegen_moves_nocheck_impl(&state);
  return state.nmoves;
}


int movegen_queen_promotions(const struct position_t* pos, move_t* buf)
{
  assert(movegen_detect_check(pos) == 0);
  static const bitboard_t mask[2] = {BB_RANK_8, BB_RANK_1};
  movegen_state_t state;
  fill_movegen_state(pos, buf, &state);
  state.mask = mask[state.stm];
  all_pawn_moves(BB_POS_PIECES(pos, state.stm, PAWN), &state);
  return state.nmoves;
}


int movegen_check_evasion(const struct position_t* pos,
			  move_t* buf)
{
  movegen_state_t state;
  fill_movegen_state(pos, buf, &state);
  bitboard_t king_attackers = movegen_detect_check(pos);
  assert(king_attackers != 0);
  movegen_check_evasion_impl(&state, king_attackers);
  return state.nmoves;
}


bitboard_t movegen_detect_check(const struct position_t* pos)
{
  assert(pos != 0);

  int stm = position_get_stm(pos);
  bitboard_t bb_king = BB_POS_PIECES(pos, stm, KING);
  int king_square = BB_LSB(bb_king);
  bitboard_t all = BB_POS_ALL(pos);

  if (!bb_king)
    return 0;
  return attackers(1 - stm, king_square, all, pos);
}


// Verification routines


move_t movegen_test_legality(const struct position_t* pos, move_t m)
{
  move_t buf[2 * MAX_N_MOVES];
  int n = movegen_legal_moves(pos, buf);
  assert(n < 2 * MAX_N_MOVES);

  /* Searches for a matching move. Two moves match if they have the
     same source and destination, and the same promotion field. When m
     has no promotion field set, the other move match if is a
     promotion to queen. */
  for (int i = 0; i < n; i++) {
    if (same_move(m, buf[i])) {
      move_t ret = buf[i];
      return ret;
    }
  }
  
  // No matching move found.
  return NULL_MOVE;
}


static int verify_king_move(const struct position_t* pos, move_t m)
{
  // Just verify that the destination square is safe
  int opponent = 1 - position_get_stm(pos);;
  int from = MOVE_FROM(m);
  int to = MOVE_TO(m);
  assert(BB_TEST(BB_POS_PIECES(pos, 1 - opponent, KING), from));

  bitboard_t all = BB_POS_ALL(pos);
  BB_CLEAR(all, from);
  BB_SET(all, to);
  return (attackers(opponent, to, all, pos) == 0);
}


static int verify_castling(const struct position_t* pos, move_t m)
{
  assert(MOVE_IS_CASTLING(m));
  bitboard_t all = BB_POS_ALL(pos);

  if (m == MOVE_WCASTLE_SHORT)
    return ((attackers(BLACK, F1, all, pos) ||
	     attackers(BLACK, G1, all, pos)) == 0);
  if (m == MOVE_WCASTLE_LONG)
    return ((attackers(BLACK, C1, all, pos) ||
	     attackers(BLACK, D1, all, pos)) == 0);
  if (m == MOVE_BCASTLE_SHORT)
    return ((attackers(WHITE, F8, all, pos) ||
	     attackers(WHITE, G8, all, pos)) == 0);
  assert (m == MOVE_BCASTLE_LONG);
  return ((attackers(WHITE, C8, all, pos) ||
	   attackers(WHITE, D8, all, pos)) == 0);
}


/*
 * Verify if the given ep capture is safe.
 *
 * Return 0 if the removal of the captured pawn leaves the king
 * exposed. Return 1 otherwise.  Does not check if other attacks may
 * be discovered by the moving pawn.
 */
static int verify_ep_capture(const position_t* pos, move_t m)
{
  assert(MOVE_ENPASSANT(m));
  assert(position_get_ep_square(pos) != NO_ENPASSANT);

  int from = MOVE_FROM(m);
  int ep = position_get_ep_square(pos);
  int stm = position_get_stm(pos);
  bitboard_t bb_king = BB_POS_PIECES(pos, stm, KING);
  int king_square = BB_LSB(bb_king);

  int captured = ep - 8 + stm * 16;
  int dir = rays[king_square][captured];
  if (dir == NULL_DIRECTION)
    return 1;

  // all and own will contain an 'updated' occupancy mask.
  bitboard_t all = BB_POS_ALL(pos);
  BB_SET(all, ep);
  BB_CLEAR(all, from);
  BB_CLEAR(all, captured);
  bitboard_t own = BB_POS_COLOR(pos, stm);
  BB_SET(own, ep);
  BB_CLEAR(own, from);

  int up = up_direction[dir];
  bitboard_t ray = slide_attacks(captured, all, up, OPP_DIRECTION(up));
  if (!BB_TEST(ray, king_square))
    return 1;
  bitboard_t att = ray & all & ~own;

  if (!att)
    return 1;  // No attackers

  assert(!BB_IS_NOT_SINGLE(att));

  // Very if the piece in ray can attack the king.
  if (att & BB_POS_PIECES(pos, 1 - stm, QUEEN))
    return 0;

  if (DIR_IS_DIAGONAL(dir))
    return ((att & BB_POS_PIECES(pos, 1 - stm, BISHOP)) == 0);

  return ((att & BB_POS_PIECES(pos, 1 - stm, ROOK)) == 0);
}


static int verify_move_pin(const position_t* pos, move_t m)
{
  int stm = position_get_stm(pos);
  int opponent = 1 - stm;
  int from = MOVE_FROM(m);
  int to = MOVE_TO(m);
  bitboard_t bb_king = BB_POS_PIECES(pos, stm, KING);
  int dir = rays[BB_LSB(bb_king)][from];
  if (dir == NULL_DIRECTION)
    return 1;

  bitboard_t all = BB_POS_ALL(pos);
  int up = up_direction[dir];
  bitboard_t ray = slide_attacks(from, all, up, OPP_DIRECTION(up));

  if (!(ray & bb_king))
    return 1;  // the king is protected by another piece

  if (BB_TEST(ray, to))
    return 1;  // the piece is moving on the same ray

  bitboard_t att = ray & BB_POS_COLOR(pos, opponent);
  if (!att)
    return 1;  // no opponent piece on the ray

  assert(!BB_IS_NOT_SINGLE(att));

  // Very if the piece in ray can attack the king.
  if (att & BB_POS_PIECES(pos, opponent, QUEEN))
    return 0;
  if (DIR_IS_DIAGONAL(dir))
    return ((att & BB_POS_PIECES(pos, opponent, BISHOP)) == 0);

  return ((att & BB_POS_PIECES(pos, opponent, ROOK)) == 0);
}


int movegen_verify_move(const struct position_t* pos,
			move_t m)
{
  int stm = position_get_stm(pos);
  bitboard_t bb_king = BB_POS_PIECES(pos, stm, KING);
  if (bb_king == 0)
    return 1;  // maybe 0 is better, or even an assertion...

  /*
   * Four kind of possible illegal moves:
   * 1) castling with intermediate attacked squares
   * 2) the king is moved in check
   * 3) the pawn captured en passant discovers the king
   * 4) a pinned piece discovers the king
   */

  int from = MOVE_FROM(m);

  if (MOVE_IS_CASTLING(m))
    return verify_castling(pos, m);
  
  if (BB_TEST(bb_king, from))
    return verify_king_move(pos, m);

  if (MOVE_ENPASSANT(m) && !verify_ep_capture(pos, m))
    return 0;

  return verify_move_pin(pos, m);
}


int movegen_is_checking(const struct position_t* pos, move_t m)
{
  /* Verify if the moving piece attacks the king, or if it cause a
     discovered check. Special rules apply to castlings, ep catpures,
     and pawn promotions. */
  int stm = position_get_stm(pos);
  int from = MOVE_FROM(m);
  int to = MOVE_TO(m);
  int p = position_get_square(pos, from);
  if (MOVE_PROMOTION(m) != NO_PROMOTION)
    p = MOVE_PROMOTION(m);
  bitboard_t king = BB_POS_PIECES(pos, 1 - stm, KING);
  int king_sq = BB_LSB(king);
  bitboard_t all = BB_POS_ALL(pos);
  BB_CLEAR(all, from);
  BB_SET(all, to);
  
  // 1) Direct attacks.
  if (p == PAWN) {
    if (movegen_pawns_left_captures(BB_SINGLE(to), stm, king) != 0)
      return 1;
    if (movegen_pawns_right_captures(BB_SINGLE(to), stm, king) != 0)
      return 1;
  } else if (p == KNIGHT) {
    if (bb_n_attacks[to] & king)
      return 1;
  } else if (p == KING) {
    if (bb_k_attacks[to] & king)
      return 1;
  } else {
    int dir = rays[king_sq][to];
    if (dir != NULL_DIRECTION) {
      if (DIR_IS_DIAGONAL(dir)) {
	if (p != ROOK && (movegen_bishop_attacks(to, all) & king) != 0)
	  return 1;
      } else {
	if (p != BISHOP  && (movegen_rook_attacks(to, all) & king) != 0)
	  return 1;
      }
    }
  }

  // 2) Checks discovered by ep-captures.
  if (MOVE_ENPASSANT(m)) {
    int ep = position_get_ep_square(pos);
    int captured = ep - 8 + stm * 16;
    BB_CLEAR(all, captured);
    bitboard_t att;
    att = movegen_bishop_attacks(king_sq, all);
    if (att & (BB_POS_PIECES(pos, stm, BISHOP) |
	       BB_POS_PIECES(pos, stm, QUEEN)))
      return 1;
    att = movegen_rook_attacks(king_sq, all);
    if (att & (BB_POS_PIECES(pos, stm, ROOK) |
	       BB_POS_PIECES(pos, stm, QUEEN)))
      return 1;
    return 0;
  }

  // 3) Castlings.
  if (MOVE_IS_CASTLING(m)) {
    int rook;
    if (m == MOVE_WCASTLE_SHORT)
      rook = F1;
    else if (m == MOVE_WCASTLE_LONG)
      rook = D1;
    else if (m == MOVE_BCASTLE_SHORT)
      rook = F8;
    else if (m == MOVE_BCASTLE_LONG)
      rook = D8;

    bitboard_t att = movegen_rook_attacks(rook, all);
    if ((att & king) != 0)
      return 1;
    return 0;
  }

  // 4) Discovered checks.
  int direction = rays[king_sq][from];
  if (direction == NULL_DIRECTION)
    return 0;
  if (DIR_IS_DIAGONAL(direction)) {
    bitboard_t att = BB_POS_PIECES(pos, stm, BISHOP);
    att |= BB_POS_PIECES(pos, stm, QUEEN);
    int up = up_direction[direction];
    bitboard_t ray = slide_attacks(king_sq, all, up, OPP_DIRECTION(up));
    if (ray & att)
      return 1;
  } else {
    bitboard_t att = BB_POS_PIECES(pos, stm, ROOK);
    att |= BB_POS_PIECES(pos, stm, QUEEN);
    int up = up_direction[direction];
    bitboard_t ray = slide_attacks(king_sq, all, up, OPP_DIRECTION(up));
    if (ray & att)
      return 1;
  }
  return 0;
}


int movegen_is_pseudo_legal(const struct position_t* pos,
			    move_t m)
{
  bitboard_t king_attackers = movegen_detect_check(pos);
  return (king_attackers
	  ? movegen_is_pseudo_legal_check(pos, m, king_attackers)
	  : movegen_is_pseudo_legal_nocheck(pos, m));
}


int movegen_see(const struct position_t* pos, move_t m)
{
  assert(pos != 0);
  assert(BB_TEST(BB_POS_ALL(pos), MOVE_FROM(m)));
  
  /* 1) Create a list of captures:
   * - a[0] is the piece in m.from
   * - a[1] is the piece in m.to
   * - a[2..n-1] contain the other attackers sorted by
   *   increasing value, and with by color alternated
   */
  bitboard_t all = BB_POS_ALL(pos);
  int stm = position_get_stm(pos);
  int a[32];
  int n = 2;
  int from = MOVE_FROM(m);
  int sq = MOVE_TO(m);

  if (MOVE_ENPASSANT(m)) {
    a[0] = pieces_values[PAWN];
    if (stm == WHITE)
      BB_CLEAR(all, sq - 8);
    else
      BB_CLEAR(all, sq + 8);
    a[1] = pieces_values[PAWN];
  } else {
    a[0] = pieces_values[position_get_square(pos, sq)];
    BB_CLEAR(all, sq);
    a[1] = pieces_values[position_get_square(pos, from)];
    if (MOVE_PROMOTION(m) != NO_PROMOTION) {
      int p = MOVE_PROMOTION(m);
      a[0] += pieces_values[p] - pieces_values[PAWN];
      a[1] = pieces_values[p];
    }
  }
  BB_CLEAR(all, from);
  
  
  /* Next piece to be tried by each side.  The pieces are tried in the
   * order: pawn, knight, bishop, rook, queen, king.  After queen, we
   * must restart from bishops, to see if a new attacker has been
   * uncovered. For the same reason, after each bishop, rook, queen or
   * king attack, the opponent must be rechecked from bishops. */
  int pi[2] = {PAWN, PAWN};
  for (;;) {
    /* A small optimization: when a capturing piece is worth more than
       the sum of its prey and its attacker, then the capture cannot
       be good enough: we can stop the capture sequence here. */
    if (n > 3 && a[n - 2] >= a[n - 1] + a[n - 3]) {
      n = n - 2;
      break;
    }
    stm = 1 - stm;
    if (pi[stm] == EMPTY)
      break;
    
    if (pi[stm] == PAWN) {
      bitboard_t tmp = pawn_attackers(stm, sq, pos) & all;
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	if (RANK(sq) == 0 || RANK(sq) == 7) {
	  // promotion
	  a[n - 1] += pieces_values[QUEEN] - pieces_values[PAWN];
	  a[n++] = pieces_values[QUEEN];
	} else {
	  a[n++] = pieces_values[PAWN];
	}
	if (pi[1 - stm] > BISHOP)
	  pi[1 - stm] = BISHOP;
	continue;
      }
      pi[stm] = KNIGHT;
    }
    if (pi[stm] == KNIGHT) {
      bitboard_t knights = BB_POS_PIECES(pos, stm, KNIGHT) & all;
      bitboard_t tmp =  knights & bb_n_attacks[sq];
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	a[n++] = pieces_values[KNIGHT];
	continue;
      }
      pi[stm] = BISHOP;
    }
    if (pi[stm] == BISHOP) {
      bitboard_t bishops = BB_POS_PIECES(pos, stm, BISHOP) & all;
      bitboard_t tmp = movegen_bishop_attacks(sq, all) & bishops;
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	a[n++] = pieces_values[BISHOP];
	if (pi[1 - stm] > BISHOP)
	  pi[1 - stm] = BISHOP;
	continue;
      }
      pi[stm] = ROOK;
    }
    if (pi[stm] == ROOK) {
      bitboard_t rooks = BB_POS_PIECES(pos, stm, ROOK) & all;
      bitboard_t tmp = movegen_rook_attacks(sq, all) & rooks;
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	a[n++] = pieces_values[ROOK];
	if (pi[1 - stm] > ROOK)
	  pi[1 - stm] = ROOK;
	pi[stm] = BISHOP;
	continue;
      }
      pi[stm] = QUEEN;
    }
    if (pi[stm] == QUEEN) {
      bitboard_t queens = BB_POS_PIECES(pos, stm, QUEEN) & all;
      bitboard_t tmp = (movegen_rook_attacks(sq, all) |
			movegen_bishop_attacks(sq, all));
      tmp &= queens;
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	a[n++] = pieces_values[QUEEN];
	if (pi[1 - stm] > BISHOP)
	  pi[1 - stm] = BISHOP;
	pi[stm] = BISHOP;
	continue;
      }
      pi[stm] = KING;
    }
    if (pi[stm] == KING) {
      bitboard_t king = BB_POS_PIECES(pos, stm, KING) & all;
      bitboard_t tmp =  king & bb_k_attacks[sq];
      if (tmp) {
	int f = BB_LSB(tmp);
	BB_CLEAR(all, f);
	a[n++] = pieces_values[KING];
	if (pi[1 - stm] > BISHOP)
	  pi[1 - stm] = BISHOP;
	pi[stm] = EMPTY;
	continue;
      }
      pi[stm] = EMPTY;
    }
    break;
  }

  /* 2) Analyze the list from the end to determine which captures are
     good enough. */
  int score = 0;
  for (int i = n - 2; i >= 0; i--) {
    if (score < 0)
      score = 0;
    score = a[i] - score;
  }
  
  return score;
}
